package Leetcode.数组字符串;

/**
 * @ClassName 盛最多水的容器
 * @since: 2023/8/9 20:03
 * @auth: kirito
 * @description:
 * https://leetcode.cn/problems/container-with-most-water/solutions/11491/container-with-most-water-shuang-zhi-zhen-fa-yi-do/?envType=study-plan-v2&envId=leetcode-75
 * 设两指针 i , j ，指向的水槽板高度分别为 h[i] , h[j] ，此状态下水槽面积为 S(i,j)。
 * 由于可容纳水的高度由两板中的 短板 决定，因此可得如下 面积公式 ：
 *
 * S(i,j)=min(h[i],h[j])×(j−i)
 *
 * 为什么让小的一边移动
 * 因为移动他们之间的间隔只可能是变小，假设间距是t，
 * s = t * height
 * 假设小的不动，高的移动，在怎么移动，就算碰到比现在还高的板子，s = t * min(height)
 * 已知间隔变小，面积也只跟两个板子中最小的板子高度相关，两个变小的数相乘，面积只会更小
 * 所以只能让高的不动，让矮的移动，可能还能遇到更高的，然后让min(height)*变小的t 的面积更大
 *
 **/
public class 盛最多水的容器 {
    public static int maxArea(int[] height) {
        int i = 0, j = height.length - 1, res = 0;
        while (i < j) {
            if (height[i] < height[j]) {
                res = Math.max(res, (j - i) * height[i]);
                i++;
            }else {
                res = Math.max(res, (j - i) * height[j]);
                j--;
            }
        }
        return res;
    }

    /**
     * 暴力
     * @param height
     * @return
     */
    public static int maxArea2(int[] height) {
        int res = 0;
        for (int i = 0; i < height.length - 1; i++) {
            for (int j = i + 1; j < height.length; j++) {
                if (height[i] < height[j]) {
                    res = Math.max(res, (j - i) * height[i]);
                }else {
                    res = Math.max(res, (j - i) * height[j]);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] num = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println(maxArea2(num));
        System.out.println(maxArea(num));
    }
}
